Many digital systems commonly employ maximum likelihood sequence detection to enhance detection of signals representing a sequence of symbols transmitted through a form of communication channel in which noise is added to the transmitted digital signal. For example, magnetic recording systems first encode data with error correction and modulation encoding, and then convert the encoded data into symbols which are recorded as a sequence of symbols on a magnetic media. The media may then be read to provide a detected sequence of symbols. A detector then employs the sequence detection algorithm to determine a most likely sequence of symbols corresponding to sequence of channel output samples read from the magnetic media.
The Viterbi algorithm (VA) employed by such systems provides a maximum a posteriori estimate of a state sequence of a finite state, discrete time Markov process observed in noise. Given a received sequence of channel output samples corrupted with additive noise, the VA finds a sequence of symbols in a trellis structure which is closest to the received channel output sample sequence according to a predefined metric. As is known, in a communication channel with additive white gaussian noise (AWGN), the VA may be shown to be the optimal maximum-likelihood (ML) sequence detection (MLSD) algorithm. Euclidian distance may be used as a metric for the trellis structure.
Also, many digital communication systems commonly employ error-control codes, or convolutional codes, to improve the probability of detection error. Telecommunication systems often perform bit interleaving after error correction en coding to minimize transmission errors from bursty noise, and then transmit the convolutionally encoded data as a symbol sequence. For example, the VA may also be used in a channel to decode an error correcting code.
Consequently, systems employing the VA recursively perform three steps, and, for convenience, the transitions between states are usually represented by a trellis structure diagram. First, branch metrics for a trellis are calculated for the current state; second, state metric updates are made for all states, and, third, the survivor paths are determined. The survivor path represents the sequence of symbols entering a given state which are closest, according to the Euclidian distance, to the received sequence of symbols in noise. The branch metric for a state is defined as the Euclidian distance between the received symbols and the ideal channel output sample corresponding to the state. To compute the entire, or global, sequence most likely received, the VA recursively calculates and updates a state metrics of all states.
As is known in the art, for the MLSD algorithm described above, the branch metric of a given transition is defined as the negative logarithm of the likelihood function with respect to the received noisy channel output sample y.sub.n, where n=1,2, . . . , and the ideal channel output sample corresponding to the transition. Therefore, the branch metric BM.sub.i,k.sup.n+1 for the transition from the ith state at time n to the kth state at time n+1, for the exemplary MLSD algorithm, is given by equation (1): EQU BM.sub.i,k.sup.n+1 =-1n f(y.sub.n -t.sub.n) (1)
where "i" represents the starting state, "n" represents time n, t.sub.n is the ideal channel output sample corresponding to the transition from the ith state to the kth state and f(*) is the probability density function of the Gaussian noise sequence.
Further, given a received sequence of y represented by a channel response polynomial H(D), where D is a delay operator, the VA recursively optimizes the most-likely path by accumulating the branch metric for each state. The number of states is given as M.sup.N, where M represents the size of the input alphabet or input levels and N denotes the channel memory length. For the VA, each state is given a state metric value at time n, and when a new value is received at time n+1, each state metric value is updated. FIG. 1A illustrates the update operation of the state metrics SM.sub.i(m) for m=(1,2, . . . M) for the transition between the i.sub.(m) th and kth states. For each of the state metrics of the trellis structure at time n+1, the previous state metrics at state i(m) (SM.sub.i(m)) at time n and the corresponding branch metric going from the i.sub.(m) th to the kth state are added together. Then the state metric for the kth state is updated to be the current SM.sub.k by choosing the minimum of all possible cases as given in equation (2): ##EQU1## where "i.sub.(m) " represents the starting state, "n" represents time n, and BM.sub.i,k.sup.a+1 represents the branch metric at time n+1 associated with the transition from the i.sub.(m) th to the kth states. For convenience, the "n" and "n+1" notation is assumed by one skilled in the art and is normally dropped.
A circuit which implements this operation is commonly referred to as the Add-Compare-Select circuit (ACS). For a binary input sequence, FIG. 2 shows an ACS circuit of the prior art which calculates the state metric value update SM.sub.k shown in FIG. 1 and given by equation (2), and for the binary case M=2. The ACS circuit 202 typically employs adders 210 and 212, a comparator 214 and a selection circuit 216, which may be a 2 to 1 multiplexer controlled by the output signal of comparator 214.
As shown in FIG. 2, adder 210 receives and combines the state metric SM.sub.i and the corresponding branch metric BM.sub.i,k into a first updated state metric, and adder 212 receives and combines the state metric SM.sub.j and the corresponding branch metric BM.sub.j,k into a second updated state metric. The first and second updated state metric values of adders 210 and 212 are compared in comparator 214, which provides a minimum indicator signal D.sub.k indicating which one of the first and second updated state metric values is a minimum value. The updated first and second state metric values and the minimum indicator signal D.sub.k are provided to selection circuit 216, which then provides the minimum one of the first and second updated state metric values as the new state metric value SM.sub.k responsive to the minimum indicator signal D.sub.k.
Since each update operation is performed serially in the ACS circuit 202 of the prior art, the ACS circuit 202 may control the speed and throughput of a system employing a VA detector. Hence, the ACS may be a bottleneck for increasing the throughput of an entire system's circuitry. Therefore, there is a need for a new state metric update structure which may increase the speed of the ACS circuit of a decoder employing the Viterbi, or similar, algorithm.